#include<iostream>
#include<vector>
using namespace std;


class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals,
        vector<int>& newInterval) {
        int len = intervals.size();
        vector<vector<int>> ans;
        if (len == 0) {
            ans.push_back(newInterval);
            return ans;
        }

        int flag = 1;
        for (int i = 0; i < len; i++) {
            if (!flag) {
                if (ans.back()[1] >= intervals[i][0] &&
                    ans.back()[1] < intervals[i][1]) {
                    ans.back()[1] = intervals[i][1];
                    continue;
                }
                else if (ans.back()[1] >= intervals[i][1]) {
                    continue;
                }
            }
            ans.push_back({ intervals[i][0], intervals[i][1] });
            if (flag && newInterval[1] > intervals[i][1] &&
                newInterval[0] < intervals[i][0]) {
                ans[i][0] = newInterval[0];
                ans[i][1] = newInterval[1];
                flag = 0;
            }
            else if (flag && newInterval[0] < intervals[i][0] &&
                newInterval[1] >= intervals[i][0]) {
                ans[i][0] = newInterval[0];
                flag = 0;
            }
            else if (flag && newInterval[0] < intervals[i][0] &&
                newInterval[1] < intervals[i][0]) {
                auto it = ans.end();
                ans.insert(--it, 1, newInterval);
                flag = 0;
            }
            else if (flag && newInterval[0] <= intervals[i][1] &&
                newInterval[1] > intervals[i][1]) {
                ans[i][1] = newInterval[1];
                flag = 0;
            }
            else if (flag && newInterval[1] <= intervals[i][1] &&
                newInterval[0] >= intervals[i][0]) {
                return intervals;
            }
        }
        if (flag) {
            ans.push_back(newInterval);
        }
        return ans;
    }
};